/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 */
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    vector<int> reversePrint_1(ListNode* head) {  //单纯使用API的方法，不做赘述
        vector<int> ans = {};
        while(head != NULL) {
            ans.push_back(head->val);
            head = head->next;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    //利用栈先进后出的特点，先压栈再出栈，可以完成逆序输出
    vector<int> reversePrint_2(ListNode* head) {
        vector<int> ans = {};
        stack<int> *s = new stack<int>();
        while(head != NULL) {
            s->push(head->val);
            head = head->next;
        }
        while(!s->empty()){
            ans.push_back(s->top());
            s->pop();
        }
        return ans;
    }

    //或者，利用递归的特性，先搜到最后一个节点，在递归返回时输出结果
    vector<int> reversePrint_3(ListNode* head) {
        vector<int> ans = {};
        recursion(head,&ans);
        return ans;
    }
    void recursion(ListNode* head, vector<int> *ans){
        if(head==NULL)
            return;
        recursion(head->next, ans);
        ans->push_back(head->val);
    }

};